/*
 * Copyright (c) 2007, Nathan Sturtevant
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met:
 *     * Redistributions of source code must retain the above copyright
 *       notice, this list of conditions and the following disclaimer.
 *     * Redistributions in binary form must reproduce the above copyright
 *       notice, this list of conditions and the following disclaimer in the
 *       documentation and/or other materials provided with the distribution.
 *     * Neither the name of the University of Alberta nor the
 *       names of its contributors may be used to endorse or promote products
 *       derived from this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY NATHAN STURTEVANT ``AS IS'' AND ANY
 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
 * DISCLAIMED. IN NO EVENT SHALL <copyright holder> BE LIABLE FOR ANY
 * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */
package com.googlecode.pathmachine.mm;

import java.util.ArrayList;
import java.util.List;

/**
 * Generic Heap
 * 
 * A relatively simple heap class. Uses a second hash table so that keys can be
 * looked up and re-heaped in constant time instead of linear time.
 * 
 * @author Nathan Sturtevant
 * @author <a href="mailto:eriq.adams@gmail.com">Eriq Muhammad Adams J.</a>
 */
public class GenericHeap {

	private List<SearchNode> _elts = new ArrayList<SearchNode>();
	private IndexTable table = new IndexTable();

	/**
	 * reset()
	 * 
	 * Remove all objects from queue.
	 * 
	 * @return none
	 */
	public void reset() {
		table.clear();
		_elts = new ArrayList<SearchNode>();
	}

	/**
	 * add()
	 * 
	 * Add object into GenericHeap.
	 * 
	 * @param val
	 *            Object to be added
	 * @return none
	 */
	public void add(SearchNode val) {
		assert (!table.containsKey(val.hash()));
		table.put(val.hash(), _elts.size());
		_elts.add(val);
		heapifyUp(table.get(val.hash()));

	}

	/**
	 * decreaseKey()
	 * 
	 * Indicate that the key for a particular object has decreased.
	 * 
	 * @param val
	 *            Object which has had its key decreased
	 * @return none
	 */
	public void decreaseKey(SearchNode val) {
		assert (val.equal(_elts.get(table.get(val.hash()))));
		_elts.set(table.get(val.hash()), val);
		heapifyUp(table.get(val.hash()));
	}

	/**
	 * GenericHeap::isIn()
	 * 
	 * Returns true if the object is in the GenericHeap.
	 * 
	 * @param val
	 *            Object to be tested
	 * @return true if the object is in the heap
	 */
	public boolean isIn(SearchNode val) {
		if ((table.containsKey(val.hash()))
				&& (table.get(val.hash()) < _elts.size())
				&& val.equal(_elts.get(table.get(val.hash())))) {
			return true;
		}
		return false;
	}

	/**
	 * remove()
	 * 
	 * Remove the item with the lowest key from the heap & re-heapify.
	 * 
	 * @return Object with lowest key
	 */
	public SearchNode remove() {
		if (empty()) {
			return new SearchNode();
		}
		SearchNode ans = _elts.get(0);
		_elts.set(0, _elts.get(_elts.size() - 1));
		table.put(_elts.get(0).hash(), 0);
		_elts.remove(_elts.size() - 1);
		table.remove(ans.hash());
		heapifyDown(0);
		return ans;
	}

	public void pop() {
		remove();
	}

	/**
	 * top()
	 * 
	 * @return first element
	 */
	public SearchNode top() {
		return _elts.get(0);
	}

	/**
	 * find()
	 * 
	 * Find this object in the heap and return
	 * 
	 * The object passed in only needs enough fields filled in to find the hash
	 * key of the object. All fields will be filled in when returned.
	 * 
	 * @param val
	 *            Object to find
	 * @return The same object from the heap.
	 */
	public SearchNode find(SearchNode val) {
		if (!isIn(val)) {
			return new SearchNode();
		}
		return _elts.get(table.get(val.hash()));

	}

	/**
	 * empty()
	 * 
	 * @return true if no items are in the heap.
	 */
	public boolean empty() {
		return _elts.isEmpty();
	}

	public int size() {
		return _elts.size();
	}

	/**
	 * heapifyUp()
	 * 
	 * Check the object at the current index and see if it needs to move up the
	 * heap.
	 * 
	 * An object moves up if it has a lower key than its parent.
	 * 
	 * @param index
	 *            Current index
	 * @return none
	 */
	private void heapifyUp(int index) {
		if (index == 0) {
			return;
		}
		int parent = (index - 1) / 2;
		if (_elts.get(parent).compare(_elts.get(index))) {
			SearchNode tmp = _elts.get(parent);
			_elts.set(parent, _elts.get(index));
			_elts.set(index, tmp);
			table.put(_elts.get(parent).hash(), parent);
			table.put(_elts.get(index).hash(), index);

			assert (!_elts.get(parent).equal(_elts.get(index)));
			heapifyUp(parent);
		}
	}

	/**
	 * heapifyDown()
	 * 
	 * Check the object at the current index and see if it needs to move down
	 * the heap.
	 * 
	 * If an object has a higher key than one or more of its children, it is
	 * swapped with its lowest-valued child.
	 * 
	 * @param index
	 *            Current index
	 * @return none
	 */
	private void heapifyDown(int index) {

		int child1 = index * 2 + 1;
		int child2 = index * 2 + 2;
		int which;
		int count = _elts.size();
		// find smallest child
		if (child1 >= count) {
			return;
		} else if (child2 >= count) {
			which = child1;
		} else if (!_elts.get(child1).compare(_elts.get(child2))) {
			which = child1;
		} else {
			which = child2;
		}

		if (!_elts.get(which).compare(_elts.get(index))) {
			SearchNode tmp = _elts.get(which);
			_elts.set(which, _elts.get(index));
			table.put(_elts.get(which).hash(), which);
			_elts.set(index, tmp);
			table.put(_elts.get(index).hash(), index);
			heapifyDown(which);
		}
	}
}
